package LeetCode;

import java.lang.module.FindException;
import java.util.ArrayList;
import java.util.List;

public class No22 {
    public static void main(String[] args) {
        generateParenthesis(3);
    }

    public static List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        char[] chars = new char[n*2];
        backTrack(0,0,list,n,chars);
        //backTrack(list,n,0,new StringBuffer());
        //dfs(0,0,n,chars,list);
        System.out.println(list);
        return list;
    }

    private static void dfs(int left, int right, int n, char[] path, List<String> ans) {
        if (right == n) { // 填完 2n 个括号
            ans.add(new String(path));
            return;
        }
        if (left < n) { // 可以填左括号
            path[left + right] = '('; // 直接覆盖
            dfs(left + 1, right, n, path, ans);
        }
        if (right < left) { // 可以填右括号
            path[left + right] = ')'; // 直接覆盖
            dfs(left, right + 1, n, path, ans);
        }
    }

    public static void backTrack(int left,int right,List<String> list,int n,char[] chars){
        if(right==n){
            list.add(new String(chars));
            return ;
        }
        if(left<n){
            chars[left+right] = '(';
            backTrack(left+1,right,list,n,chars);
        }
        if(right<left){
            chars[left+right]=')';
            backTrack(left,right+1,list,n,chars);
        }
    }

    public static void backTrack(List<String> list, int n, int index,StringBuffer s){
        for (int i = index; i < n; i++) {
            s.append("(");
            backTrack(list,n,index+1,s);
            s.append(")");
            if(s.length()==n*2)
                list.add(s.toString());
            s.delete(s.length()-2,s.length());
        }
    }
}
